package Path;

import java.util.Arrays;

public class Path {
    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] board= {{'a','b'},{'c','d'}};
        String word = "abcd";
        boolean ans =s.exist(board, word);
        System.out.println(ans);
    }
}

// 剑指 Offer 12. 矩阵中的路径
/**
 * 一个纯深度优先搜索
 */
class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] vis = new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            Arrays.fill(vis[i], false);
        }
        //首先不知道从哪开始,所以要每个点都循环一次
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(search(i, j, word, 0, vis, board)) return true;
            }
        }
        return false;
    }

    //只有4个方向
    int[] X = {-1,0,0,1};
    int[] Y ={0,-1,1,0};

    public boolean search(int x,int y,String word,int n,boolean[][]vis,char[][] board){
        // if(n==word.length())return true;
        if(board[x][y]==word.charAt(n)){
            if(n==word.length()-1) return true;
            vis[x][y] = true;
            for(int i=0;i<X.length;i++){
                    //x 和 y是对应的,所以只需要一个循环就行
                    int nx = x+X[i];
                    int ny = y+Y[i];
                    if(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length&&!vis[nx][ny]){
                        boolean res = search(nx, ny, word, n+1, vis, board);
                        if(res) return true;
                    }
                }
            vis[x][y] = false;
        }
        return false;
    }
}

